Field of the Disclosure
This application relates to sorting and in particular to sorting using multiple processing units.
Description of the Related Art
The widely accepted value for the minimum number of comparison operations to sort a large list of N elements is N log 2(N). Sorting a very large list of one billion items, for example, still requires roughly 30B comparisons. Each of these comparisons can also require many clock cycles of the computing system. 30B comparisons might actually take 300B clocked operations. In Big Data analytics, weather prediction, nuclear calculations, astrophysics, genetics, public health, and many other disciplines, there is a frequent need to sort very large datasets. This further implies computational resources than can literally fill buildings with racks of servers to service these needs. To the extent one can improve on this N log 2(N) limitation on sorts (with multiple operations per sort), one can improve on the capital infrastructure and associated operational costs for computing systems.